A
弱智题,统计一下每行每列的和即可。
时间复杂度 。
Code
#include <cstdio>
const int N = 35;
int a[N][N], row[N], col[N], n, res;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
row[i] += a[i][j];
col[j] += a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (col[j] > row[i]) res++;
}
printf("%d\n", res);
}
B
对半径从大到小排序,顺次模拟即可。
时间复杂度 。
Code
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const double pi = acos(-1);
double r[N], res;
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf", &r[i]);
sort(r + 1, r + n + 1);
reverse(r + 1, r + n + 1);
for (int i = 1; i <= n; i++) {
if (i & 1) res += pi * r[i] * r[i];
else res -= pi * r[i] * r[i];
}
printf("%.10lf\n", res);
}
C
由于插入和删除都是在头尾进行的,可以枚举 的左端点在 中的位置,暴力匹配即可。
时间复杂度 。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2005;
char a[N], b[N];
int main() {
scanf("%s%s", a + 1, b + 1);
int n = strlen(a + 1);
int m = strlen(b + 1);
int ans = m;
for (int i = -m; i <= n; i++) {
int res = m;
for (int j = 1; j <= m; j++) {
if (i + j <= 0 || i + j >= n + 1) continue;
if (a[i + j] == b[j]) res--;
}
ans = min(ans, res);
}
printf("%d\n", ans);
}
D
有趣的推理题。
对于每一个人,设 为指控这个人是罪犯的人数, 为指控这个人不是罪犯的人数。
先假设所有人都不是罪犯,处理出来 与 的值,同时记录 句话中真话数量 。
然后我们让每个人尝试成为罪犯。如果 成为罪犯,那么 和 将会互换。原本 句真话中有 句会变为假话, 句变为真话。
而一共有 句真话,所以当且仅当
时 才有可能成为罪犯。我们记录下来可能成为罪犯的人以及可能成为罪犯的人数。
然后就可以输出了。对于第 句话,判断一下这句话指控的人是否可能为罪犯以及罪犯人数即可。
时间复杂度 。
Code
#include <cstdio>
const int N = 1e5 + 5;
int n, m, s, cnt, a[N], sus[N], con[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] > 0) con[a[i]]++;
else con[-a[i]]--, s++;
}
for (int i = 1; i <= n; i++)
if (con[i] + s == m) {
cnt++;
sus[i] = 1;
}
for (int i = 1; i <= n; i++) {
if (a[i] > 0) {
if (!sus[a[i]]) puts("Lie");
else if (cnt == 1) puts("Truth");
else puts("Not defined");
} else {
if (!sus[-a[i]]) puts("Truth");
else if (cnt == 1) puts("Lie");
else puts("Not defined");
}
}
}
E
我们将字符 到 对应为 至 ,容易发现每一次操作整个串的和是不变的。
由于操作可以传递,变换相邻字符的操作可以经过若干次操作变成变换任意两个字符。于是问题就变成了给定总和求字符串个数。
很显然的dp。设 为字符串 的前 位和为 的总数。转移方程显然
由于多组数据,我们可以先预处理 ,询问直接输出即可。
时间复杂度 。
Code
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 105;
const int mod = 1e9 + 7;
int f[N][N * 26], n, sum, T;
char s[N];
int main() {
f[0][0] = 1;
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 2600; j++)
for (int k = 1; k <= min(j, 26); k++)
f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
}
scanf("%d", &T);
while (T--) {
scanf("%s", s);
sum = 0;
n = strlen(s);
for (int i = 0; i < n; i++) sum += s[i] - 'a' + 1;
printf("%d\n", f[n][sum] - 1);
}
}